package algorithm.t202111;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/8 10:49
 * @description :4道
 * 一个git，没有整好
 * persevere to last
 * 2021.11.08
 * 2021年11月8日21:06:39
 * 李红磊
 */
public class t20211108 {

    //299.猜数字游戏
    public String getHint(String secret, String guess) {
        if (secret.equals(guess)) {
            return secret.length() + "A0B";

        }

        int count_a = 0, count_b = 0;//记录AB的数量
        HashMap<Character, Integer> map_secret = new HashMap<>();
        HashMap<Character, Integer> map_guess = new HashMap<>();


        for (int i = 0; i < guess.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                count_a++;
                continue;
            }
            //若两者不匹配，则放入各自的哈希表
            map_guess.put(guess.charAt(i), map_guess.getOrDefault(guess.charAt(i), 0) + 1);
            map_secret.put(secret.charAt(i), map_secret.getOrDefault(secret.charAt(i), 0) + 1);

        }
        Set<Character> sere_key = map_secret.keySet();

        //对哈希表进行处理
        for (Character character : sere_key) {
            if (map_guess.containsKey(character)) {//说明两者存在【奶牛】，至于数量多少要经过处理
                if (map_guess.get(character) == map_secret.get(character)) {//若两者该数出现的次数相等，这个次数就指是数字对而位置不对的数字位数
                    // 直接给B赋值
                    count_b += map_guess.get(character);
                    continue;
                } else if (map_guess.get(character) > map_secret.get(character)) {//guess中该数的出现次数大于 secret中出现的次数，
                    //将guess中捡到和secret相等，就是B的值
                    while (map_guess.get(character) != map_secret.get(character)) {
                        map_guess.put(character, map_guess.get(character) - 1);
                    }
                    count_b += map_guess.get(character);
                    continue;
                } else {
                    while (map_guess.get(character) != map_secret.get(character)) {
                        map_secret.put(character, map_secret.get(character) - 1);
                    }
                    count_b += map_guess.get(character);
                    continue;
                }

            }

        }
        return count_a + "A" + count_b + "B";
    }

    //300.最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return len;
        }

        int[] dp = new int[len];
        Arrays.fill(dp, 1);

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }

            }
        }

        int res = 0;
        for (int i : dp) {
            res = Math.max(res, i);
        }
        return res;
    }

    //673.最长递增子序列的个数 LIS LongestIncreasingSequence
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        if (len < 2) return len;

        int[] dp = new int[len];//记dp[i]:表示以nums[i]结尾的递增子序列（LIS)的长度
        int[] count = new int[len];//count[i]:表示以nums[i]结尾的LIS的组合个数
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                    } else if (dp[i] == dp[j] + 1) {
                        count[i] += count[j];
                    }
                }
            }
        }

        int max_len = 1;
        for (int i : dp) max_len = Math.max(max_len, i);

        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] == max_len) {
                res += count[i];
            }
        }

        return res;
    }

    //面试题16.10 生存人数
    public int maxAliveYear(int[] birth, int[] death) {
        int[] arr = new int[102];
        for (int i = 0; i < birth.length; i++) {
            arr[birth[i] - 1900]++;
            arr[death[i] - 1900 + 1]--;
        }
/*
    好好思考。假如一个1901年出生，1902死亡，我们看看作他在1901和1902都活着，当到了1903年时才真正消失
    有birth[1900,1901,1950]
     death[1948,1951,2000]

     可以看作，在0年出生一个，1年出生一个，49年死一个，50年出生一个，52年死一个，101年死一个。故可以看出，在2年存活人数最多（年数取小
 */
        int curAlive = 0;
        int maxCurAlive = 0;//是
        int year = 1900;

        for (int i = 0; i < arr.length; i++) {
            curAlive += arr[i];
            if (curAlive > maxCurAlive) {
                maxCurAlive = curAlive;
                year += i;
            }

        }

        return year;
    }


    public static void main(String[] args) {
        t20211108 t20211108 = new t20211108();
        System.out.println(t20211108.getHint("1807", "7810"));
    }
}
